package DataStructure.heap;

//堆,堆顶维护的是一个界限,小根堆对应大值下界,大根堆对应小值上界
public class  Heap <E extends Comparable<E>> implements MyHeap<E>{
    private E[] e;
    private int size;
    private final boolean isMin;//是否为小根堆

    public Heap(int cap,boolean min) {
        e= (E[]) new Comparable[cap+1];//0位置不使用
        size=0;
        isMin=min;
    }
    //判断大小
    private boolean lt(int i,int j){
        return isMin?e[i].compareTo(e[j])<0:e[i].compareTo(e[j])>0;
    }
    //交换节点
    private void swap(int i,int j){
        E tmp=e[i];
        e[i]=e[j];
        e[j]=tmp;
    }
    //向上调整
    private void swim(int i){
        while (i>1){
            if(lt(i/2,i)) break;
            //子节点较小则上浮
            swap(i/2,i);
            i/=2;
        }
    }
    //向下调整
    private void sink(){
        int i=1;
        //当i节点存在子节点
        while (i*2<=size){
            int min=i*2;
            //当存在右子节点且较小
            if(i*2+1<=size && lt(i*2+1,i*2))
                min=i*2+1;
            if(lt(i,min)) break;
            //父节点较小则下沉
            swap(i,min);
            i=min;
        }
    }

    @Override
    public E peek() {
        return e[1];
    }

    @Override
    public void push(E e) {
        if(size+1==this.e.length) return;
        this.e[++size]=e;//放在末尾
        swim(size);//向上调整
    }

    @Override
    public E poll() {
        if(isEmpty()) return null;
        E min=e[1];//取堆顶
        swap(1,size--);//堆顶与末尾交换
        sink();//交换后堆顶向下调整
        return min;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void clear() {
        e= (E[]) new Comparable[4];
        size=0;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder("[");
        for (int i = 1; i <= size; i++) {
            sb.append(e[i]);
            if(i!=size)
                sb.append(",");
        }
        sb.append("]");
        return "Heap{" +
                "e=" + sb +
                ", size=" + size +
                '}';
    }
}
